package com.kevinkk.monotonicstack;

import java.util.*;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */

public class TrappingRainWater {
    /**
     * 双指针
     * left  记录每个元素左边的最大元素
     * right 记录每个元素右边的最大元素
     * 每个元素能够装水的面积为
     *      高度：Math.min(left[i], right[i]) - height[i]
     *      宽度： 1
     */
    class Solution1 {
        public int trap(int[] height) {
            int length = height.length;
            int[] left = new int[length], right = new int[length];
            left[0] = height[0];
            for (int i = 1; i < length; i++)
                left[i] = Math.max(left[i - 1], height[i]);

            right[length - 1] = height[length - 1];
            for (int i = length - 2; i >= 0; i--)
                right[i] = Math.max(right[i + 1], height[i]);

            int res = 0;
            for (int i = 0; i < length; i++) {
                int area = Math.min(left[i], right[i]) - height[i];
                res += area;
            }
            return res;
        }
    }


    /**
     * 单调栈
     */
    class Solution2 {
        public int trap(int[] height) {
            Deque<Integer> st = new ArrayDeque<>();
            int res = 0;
            for (int i = 0; i < height.length; i++) {
                // 右边的高的元素 height[i]
                while (!st.isEmpty() && height[i] > height[st.peekFirst()]) {
                    int mid = st.removeFirst();
                    if (!st.isEmpty()) {
                        // 由于是一个单调递增的栈，因此此时栈顶的元素依旧比 height[mid] 大
                        // 因此左边的高的元素 height[st.peekFirst()]
                        int h = Math.min(height[i], height[st.peekFirst()]) - height[mid];
                        int w = i - st.peekFirst() - 1;
                        res += h * w;
                    }
                }
                st.addFirst(i);
            }

            return res;
        }
    }
}
